#include "./string-match.h"
#include <string.h>

int indexOf(char *s, char *t)
{
	int i, j, sLen, tLen;
	i = j = 0;
	sLen = strlen(s);
	tLen = strlen(t);
	while (i < sLen && j < tLen)
	{
		// 开始逐个比较
		if (s[i] == t[j])
		{
			i++;
			j++;
		}
		else
		{
			// 失配时，把i定位到开始比较的时候所在位置的下一个，j定位为0
			i = i - j + 1;
			j = 0;
		}
	}
	if (j >= tLen)
	{
		// 若j位于模式串最后个字符后面说明是匹配完成了
		return i - tLen;
	}
	return -1;
}

int *getNext(char *t)
{
	int length = strlen(t);
	int *next = (int *)malloc(length * sizeof(int)), m = 0, n = 1;
	next[0] = -1;
	next[1] = 0;
	while (n < length - 1)
	{
		if (m == -1 || t[m] == t[n])
		{
			m++;
			n++;
			next[n] = m;
		}
		else
		{
			m = next[m];
		}
	}
	return next;
}

int kmpIndexOf(char *s, char *t)
{
	int i = 0, j = 0;
	int sLen = strlen(s);
	int tLen = strlen(t);
	int *next = getNext(t);
	while (i < sLen && j < tLen)
	{
		if (j == -1 || s[i] == t[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j > tLen - 1)
	{
		return i - tLen;
	}
	return -1;
}